import java.util.ArrayList;
import java.util.Arrays;

public class Leetcode {
}

//leetcode:611:有效三角形的个数
class Solution {
    public int triangleNumber(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);
        int ret = 0;
        for(int i = 0;i< n;i++){
            int k = i;
            for(int j = i+1;j< n;j++){
                while(k+1<n && nums[k+1] < nums[i] + nums[j]){
                    k++;
                }
                ret += Math.max(k-j,0);
            }
        }
        return ret;
    }
}

//和为s的两个数字
class Solution2 {
    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        ArrayList<Integer> list = new ArrayList<>();
        int n = array.length;
        int left = 0,right = n-1;
        while(left < right){
            int tmp = array[left] + array[right];
            if(tmp == sum){
                list.add(array[left]);
                list.add(array[right]);
                return list;
            }else if(tmp < sum){
                left++;
            }else{
                right--;
            }
        }
        return list;

    }
}